package com.zfl;

public class MaxPathSum {
    private int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        getMax(root);
        return this.maxSum;
    }

    private int getMax(TreeNode root) {
        if(root==null)
            return 0;

        int left = Math.max(this.getMax(root.left),0);
        int right = Math.max(this.getMax(root.right),0);

        int sum = left+right+ root.val;
        this.maxSum = Math.max(this.maxSum,sum);

        return Math.max(left,right)+root.val;
    }
}
